package bstsetcode.stanforduniversity18;

import java.util.ArrayList;
import java.util.List;

/**
 * @author noob
 * @version 1.0
 * @date 2021/3/15 21:02
 * 讲一个链表分成前后两个链表
 */
public class _09_FrontBack {

    /**
     * 将一个链表分成前后两个链表，如果是奇数就差1
     * @param head
     * @return
     */
    public static final Integer NUM=2;
    public static List<ListNode> frontBackSplit(ListNode head){
        ListNode headA;
        ListNode headB;

        if (head == null){
            return  null;
        }
        //count 链表的长度
        int count=0;
        ListNode cur = head;
        while (cur!=null){
            cur = cur.next;
            count++;
        }
        if(count< NUM){
            List<ListNode>  list = new ArrayList<>();
            headA = head;
            headB = null;
            list.add(headA);
            list.add(headB);
            return list;
        }

//        当count>=2的时候
        int hopCount;
        if((count & 1) == 0){
//            如果是偶数
            hopCount = count /2;
        }else{
            hopCount = (count-1)/2;
        }


        ListNode cur1 = head;
        for (int i = 0; i < hopCount-1; i++) {
            cur1=cur1.next;
        }

        headB = cur1.next;
        cur1.next = null;
        headA =head;
        List<ListNode> list1 = new ArrayList<>();
        list1.add(headA);
        list1.add(headB);
        return  list1;

    }

    public static void main(String[] args) {
        int[] nums2 = {5,6,7,8};
        int[] nums3 = {5,6,7,8,9};
        ListNode headB = new ListNode(nums3);
        List<ListNode> listNodes = _09_FrontBack.frontBackSplit(headB);
        for(ListNode n:listNodes){
            System.out.println(n);
        }
    }
}
